A heterogeneous resource cloud generally comprises a set of physical resources of multiple types that can be leveraged to provide desirable services to end users. A virtual appliance is one example of such a potentially desirable service. Generally speaking, a virtual appliance is a pre-configured emulation of an electronic device or system, such as a computer, workstation, server, router, switch, hard drive, or disk array, for example. In response to a request for a particular virtual appliance service, a cloud service provider may select resources from among those of a heterogeneous resource cloud and use the selected resources to provide the request service. The cloud service provider may typically benefit from some degree of flexibility with respect to such resource selection—there may be numerous resources within a given heterogeneous resource cloud that can be used to perform the necessary emulation. However, depending on the nature of the device to be emulated, the requirements/preferences of the end user and/or virtual appliance vendor, the requirements of any applicable service level agreement (SLA), and/or other factors, there may also be constraints on the resources that can be used to provide any particular virtual appliance service.